#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string>  ans;
        int n = words.size();
        vector<string> t;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (cnt + words[i].size() <= maxWidth) {
                t.push_back(words[i]);
                cnt += words[i].size();
                cnt++;
            }
            else {
                string str = "";
                int k = maxWidth - (cnt - t.size());
                int cc = t.size() - 1;
                for (int j = 0; j < t.size(); j++) {
                    str += t[j];
                    int kg = 0;
                    if (j != t.size() - 1) {
                        int kg = (k + cc - 1) / cc;
                        string ss = "";
                        for (int z = 0; z < kg; z++)ss += ' ';
                        str += ss;
                        k -= kg;
                        cc--;
                    }
                    else if (k) {
                        string ss = "";
                        for (int z = 0; z < k; z++)ss += ' ';
                        str += ss;
                    }
                }

                ans.push_back(str);
                t.clear();
                t.push_back(words[i]);

                cnt = words[i].size();
                cnt++;
            }
        }
        string str = "";
        for (int i = 0; i < t.size(); i++) {
            str += t[i];
            if (str.size() < maxWidth)str += ' ';
        }
        int sz = str.size();
        for (int i = 0; i < maxWidth - sz; i++)str += ' ';

        ans.push_back(str);
        return ans;
    }
};